package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/18 13:03
 *
 二叉树的下一个节点：

 自己想的：找到根节点，然后进行中序遍历，用哈希表存储该节点的下一节点，
 然后直接返回map.get()——空间O(n),时间O(n)

 不使用map：找到根节点，进行中序遍历，维护ans 空间O(1)

题解做法：分三种情况讨论,非递归
L，Root，R
1，当前节点有R节点，则模拟递归查找其右子树
2，当前节点无右节点且为上一节点的左节点，则下一节点就是其父节点
3，当前节点无右节点且为上一节点的R节点，则需要向上爬树，直到该节点为其父节点的左子树中的点
4，空节点

 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Main39 {
    class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;

        TreeLinkNode(int val) {
            this.val = val;
        }
    }


    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if(pNode==null)return null;
        if(pNode.right!=null){
            TreeLinkNode t=pNode.right;
            while (t.left!=null){
                t=t.left;
            }
            return t;
        }
            //右节点为空
            //为左节点
            if(pNode.next!=null&&pNode.next.left==pNode){
                return pNode.next;
            }
            //为右节点
            if(pNode.next!=null){
                TreeLinkNode t=pNode;
                while(t.next.left!=t){
                    t=t.next;
                }
                return t;
            }
            return null;
    }

    //上一个节点
    TreeLinkNode pre=null;
    TreeLinkNode ans;
    public void dfs(TreeLinkNode root,TreeLinkNode pNode){
        if(root==null)return;
        dfs(root.left,pNode);
        //通过调试：当pre一定时，root是变化的，
        //pre的下一个点，因为是递归的，所以root要走到尽头，所以要去最终值
        if(pre!=null)System.out.println("pre:"+pre.val+",root:"+root.val);
        if(pre==pNode){
            ans=root;
            //不能return，因为找到pre之后，root还需要递归的走到尽头
            //return;
        }
        pre=root;
        dfs(root.right,pNode);
    }

    public TreeLinkNode GetNext2(TreeLinkNode pNode) {
        if(pNode==null)return null;
        TreeLinkNode root=pNode;
        while(root.next!=null){
            root=root.next;
        }
         dfs(root,pNode);
        return ans;
    }
    /*
    TreeLinkNode pre=null;
    HashMap<TreeLinkNode,TreeLinkNode>map=new HashMap<>();
    public void  helper(TreeLinkNode root){
        if(root==null)return ;
        helper(root.left);
        map.put(pre,root);
        pre=root;
        helper(root.right);
    }


    //入参只有8这个节点
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if(pNode==null)return null;
        TreeLinkNode root=pNode;
        while(root.next!=null){
            root=root.next;
        }
        helper(root);
        return map.get(pNode);
    }
    */
}
